package com.zdp.leetcodeMiddle;

import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 括号生成_22 {
    public static void main(String[] args) {
        括号生成_22 demo = new 括号生成_22();
        List<String> strings = demo.generateParenthesis(3);
        for(String item : strings){
            System.out.println(item);
        }
        System.out.println("解法2");
        List<String> strings1 = demo.generateParenthesis2(3);
        for(String item : strings1){
            System.out.println(item);
        }
    }

    /*
    * 解法一：生成所有可能的序列，然后判断是否为正确的序列
    * 每个index+1 的序列都是在index序列的基础上 加上( 或者 )
    * */
    public List<String> generateParenthesis(int n) {
        char[] current = new char[2*n]; //当前序列
        List<String> result = new ArrayList<>();
        all(current,0,current.length,result);
        return result;
    }
    public void all(char[] cur,int index,int length,List<String> result){
        if(index == length){
            // 判断是否正确
            if(valid(cur)){
                result.add(new String(cur));
            }
        }else{// 如果还没有生成完毕，就添加( 或者 )
            // 添加左括号
            cur[index] = '(';
            all(cur,index+1,length,result);
            // 添加右括号
            cur[index] = ')';
            all(cur,index+1,length,result);
        }
    }
    public boolean valid(char[] cur){
        int balance = 0;
        for(int i=0;i<cur.length;i++){
            if(cur[i]=='('){
                balance++;
            }else{
                balance--;
            }
            if(balance<0){
                return false;
            }
        }
        return balance ==0;
    }

    /*
    * 解法二：保证每次添加后，序列都是有效的 也就是 只在序列有效的情况下进行添加，
    * 添加后的序列也应该保持有效
    * 如何判断添加后的序列是有效的？
    * 首先，只有在左括号的数量小于n时才可以添加左括号
    * 其次，右括号的添加也应该是在 有括号的数量小于左括号时才可以添加
    * 还有，因为左括号应该在右括号的左边，所以左括号的添加操作应该比右括号前
    * */
    public List<String> generateParenthesis2(int n) {
        StringBuilder current = new StringBuilder();//当前序列
        List<String> result = new ArrayList<>();
        all2(current,0,0,n,result);
        return result;
    }
    public void all2(StringBuilder cur,int left,
                     int right,int n,List<String> result){
        if(cur.length()==2*n){
            result.add(new String(cur));
        }else{
            // 在正确的序列的基础上进行添加括号操作
            if (left < n){
                // 左括号数量还未满
                cur.append('(');
                all2(cur,left+1,right,n,result);
                // 回溯，应该将刚才添加的左括号删除
                cur.deleteCharAt(cur.length()-1);
            }
            if(right < left){
                // 有括号的数量少于左括号，可以进行添加
                cur.append(')');
                all2(cur,left,right+1,n,result);
                // 回溯
                cur.deleteCharAt(cur.length()-1);
            }
        }
    }
}
